package class8;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 堆结构
 * [0, 1, 2, 3, 4, 5, 6]
 * *     0
 * *   1  2
 * *  34  56
 * 公式：
 * 左孩子： 2*i+1
 * 右孩子： 2*i+2
 * 父节点： (i-1)/2
 * ---
 * 节点0左：2*0+1 = 1   节点1左：2*1+1 = 3  节点2左：2*2+1 = 5
 * 节点0右：2*0+2 = 2   节点1右：2*1+2 = 4  节点2右：2*2+2 = 6
 * ----
 * 节点4父： (4-1)/2 = 1 节点6父：(6-1)/2 = 2
 * <p>
 * 扩展
 * 也可能从1开始[_,1,2,3,4,5,6,7],0不用
 * *     1
 * *   2  3`
 * *  45  67
 * 这种设计是因为<<1比*2更快
 */
public class Code08_HeapConstruct {
    public static void main(String[] args) {
//        leftSon();
//        rightSon();


        // 小根堆
        PriorityQueue<Integer> p = new PriorityQueue();
        p.add(3);
        p.add(8);
        p.add(4);
        p.add(5);
        p.add(2);
        System.out.println(p.poll());
    }

    /**
     * 左边向下遍历
     */
    private static void leftSon() {
        int[] heap1 = new int[]{0, 1, 2, 3, 4, 5, 6};
        int len = heap1.length;
        int i = 0;
        // 遍历左子节点
        while (i < len) {
            int cur = heap1[i];
            System.out.print(cur + "\t");
            i = i * 2 + 1;
        }
        System.out.println();
    }

    /**
     * 右孩子向下遍历
     */
    private static void rightSon() {
        int[] heap1 = new int[]{0, 1, 2, 3, 4, 5, 6};
        int len = heap1.length;
        int i = 0;
        // 遍历左子节点
        while (i < len) {
            int cur = heap1[i];
            System.out.print(cur + "\t");
            i = i * 2 + 2;
        }
        System.out.println();
    }

    private static void leftSon2() {
        int[] heap2 = new int[]{0, 1, 2, 3, 4, 5, 6, 7};
        int len2 = heap2.length;
        int i2 = 1;
        // 遍历左子节点
        while (i2 < len2) {
            int cur = heap2[i2];
            System.out.print(cur + "\t");
            i2 <<= 1;
        }
        System.out.println();
    }
}
